{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 匈牙利算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 匈牙利算法介绍\n",
    "from scipy.optimize import linear_sum_assignment\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果要求的问题是求和最小问题，那么这个矩阵就叫做花费矩阵（Cost Matrix）,  \n",
    "如果要求的问题是使之和最大化，那么这个矩阵就叫做利益矩阵（Profit Matrix）."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 算法流程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "首先进行列规约，即每行减去此行最小元素，每一列减去该列最小元素，规约后每行每列中必有0元素出现。接下来进行试指派，也就是划最少的线覆盖矩阵中全部的0元素，如果试指派的独立0元素数等于方阵维度则算法结束，如果不等于则需要对矩阵进行调整，重复试指派和调整步骤直到满足算法结束条件。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "cost = np.array([[90,75,75,80],[35,85,55,65],[125,95,90,105],[45,110,95,115]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "x,y = linear_sum_assignment(cost)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "行索引: [0 1 2 3] 列索引 [1 3 2 0]\n"
     ]
    }
   ],
   "source": [
    "print('行索引:',x,'列索引',y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "对应的值: [75 65 90 45]\n"
     ]
    }
   ],
   "source": [
    "print(\"对应的值:\",cost[x,y])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "和: 275\n"
     ]
    }
   ],
   "source": [
    "print(\"和:\",cost[x,y].sum())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 1), (1, 3), (2, 2), (3, 0)]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(zip(x,y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 1],\n",
       "       [1, 3],\n",
       "       [2, 2],\n",
       "       [3, 0]], dtype=int64)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.array(list(zip(x,y)))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}